package wangn.procedure;

import wangn.adt.CFG;
import wangn.adt.ItemSetNode;
import wangn.adt.base.More;
import wangn.adt.base.Pair;
import wangn.adt.base.Tri;

import java.util.*;

/**
 * 构造LR（1）项目集
 * 输入：增扩文法G‘
 * 输出：LR（1）项目集
 *
 * 总体方法是使用BFS对一棵n叉树进行扩展
 *
 * 构造方法如下：
 * 1、首先为当前的文法增加0产生式变成G‘，用@符号指代0号产生式的左部（这步调到CFG构造时候完成）
 * 2、第一步，将@->·G,$作为I_0,分析式的开始
 * 3、进入I_i，依次扫描各项目，若点在最后一个字符的后面就跳过，根据点后的字符填入所有项目后进入第4步，如果没有下一项就完成并且返回n叉树
 * 4、依据点后面的字符e（Vt或者Vn）开始进行扩展（制造下一项，记为I_i+1），填入这个产生式（点已经后移），
 *    然后把e作为左部的所有产生式（从这个产生式子后面起）填入（点在首位），然后再次扫描I_i，填入所有点后面是e的产生式以及其扩展
 *    检测符通过FIRST（e后面的字符以及检测符组成的字符串）进行求解
 * 5、现在已经构建了一个完整的项I_i+1，然后判断它是否有弱相等的项j（只有检测符不同）：
 *    （1）如果有，合并他们的检测符然后记合并后的项的状态为j，并且令i+1=j，该项放入I_i的子节点中，该分支已经到叶节点，返回
 *    （2）如果无，则将该项放入I_i的子节点中，然后将I_i+!作为I_i回到第3步（bfs）
 */
public class LRItemTree {

    private ItemSetNode head;
    private List<ItemSetNode> nodeList = new ArrayList<>();//include all the nodes that have unique state number

    private CFG cfg;
    private int I_i = 0;//表示状态的数字

    public ItemSetNode constructLRItemTree(CFG cfg){
        /**
         * 这里对BFS构造节点做好所有准备：
         * 1、grammar文法的所有产生式的列表，用于扫描--》全局
         */
        this.cfg = cfg;
        head = new ItemSetNode(I_i++);
        head.addItem(0,0,new More<>('$'));
        head = bfs(head);
        return head;
    }

    /**
     *
     * @function 对当前节点（已经插入过某一个状态的所有产生式）进行扩展--根据点后面的字符增加项然后填充其孩子
     *           顺序是：
     *           1、扫描每一项，记录点后的字符e（终结符或者是非终结符），若字符已经扩展过就跳过，否则进入第2步
     *           2、将该项以及之后所有点后是e的项加入新的节点中（点已经移动，且计算了检测符，重复的项考虑合并检测符），新节点加入原来节点的children中，
     *              回到1直到不能再加入，
     *           3、对该项进行检测，如果已经有了一样的项就选择合并或者直接改变这一项，为了影响父亲，如果该项重复了就改变state number
     *           3、对children进行bfs调用，如果state number已经存在说明重复了，改变父节点指向对应state的节点然后跳过，否则加入待bfs调用的队列
     * @param node 当前需要扩展的节点
     * @return ItemSetNode 返回该节点更新后，用于当前节点和已经有的节点重复的情况
     *
     */
    private ItemSetNode bfs(ItemSetNode node){
        int i = 0;
        Map<String,Integer> visitedItemMap = new HashMap<>();

        if (nodeList.contains(node))return node;
        nodeList.add(node);

        while (i < node.getLength()){
            Tri<Integer,Integer,More<Character>> lr1Item = node.getItem(i);
            i++;
            Pair<String,String> grammar = cfg.getGrammar(lr1Item.getFirst());
            if (lr1Item.getSecond()>=grammar.getSecond().length())continue;//tail
            char e = grammar.getSecond().charAt(lr1Item.getSecond());

            //不要检查是否已经扩展过，因为扩展过程是动态的，通过比对当前项里面的前两个数字来确定重复的项（都需要合并第三项）
            //然后把CFG中以e为左的产生式全部加进去，这里注意，加进去以后仍然需要扩展，但是仅扩展一步
            //如果没有这样的产生式就直接跳过，此时应该是vt项
            List<Integer> sameLeftProducts = cfg.findSameLeftProducts(e+"");
            if (sameLeftProducts.isEmpty())continue;
            for (int productIdx : sameLeftProducts){//否则寻找其在cfg中的e为左部的所有产生式
                Pair<String,String> gram = cfg.getGrammar(productIdx);//同左部的所有产生式
                //有相同项，则考虑合并
                if (visitedItemMap.containsKey(gram.getFirst()+","+gram.getSecond())){
                    int sameId = visitedItemMap.get(gram.getFirst()+","+gram.getSecond());
                    Tri<Integer,Integer,More<Character>> tri = node.getItem(sameId);//已有的项
                    String flags = tri.getSecond() >= cfg.getGrammar(tri.getFirst()).getSecond().length()
                            ?"":cfg.getGrammar(tri.getFirst()).getSecond().charAt(tri.getSecond())+"";
                    More<Character> mores = FIRST.first(cfg,flags);
                    if (mores.getLength()==0){
                        mores = lr1Item.getThird();
                    }
                    mores = unionCheckFlag(mores,tri.getThird());
                    tri.setThird(mores);
                    node.setItem(sameId,tri);
                }else{//否则需要建立新项
                    visitedItemMap.put(gram.getFirst()+","+gram.getSecond(),node.getLength());//id from 0
                    String flags = lr1Item.getSecond()+1 >= cfg.getGrammar(lr1Item.getFirst()).getSecond().length()
                            ?"":cfg.getGrammar(lr1Item.getFirst()).getSecond().charAt(lr1Item.getSecond()+1)+"";
                    More<Character> mores = FIRST.first(cfg,flags);
                    if (mores.getLength()==0){
                        mores = lr1Item.getThird();
                    }
                    node.addItem(productIdx,0,mores);//从cfg中得到，所以点在最左边，
                }
            }
        }

        boolean needAddChild = true;

        //到这里已经扩展完毕，需要检测当前项是否和已有的项重合，包括：
        //1、若强相等，则直接使用相等的项（改变本项的state number）
        //2、若弱相等，则将本项的检测符合并进入已有，然后直接返回新的节点
        //3、在1或者2情况下，不需要扩展孩子

        //LR文法中不要合并同同心项
        String simpleHashValue = node.getSimpleHashValue();
        String realHashValue = node.getRealHashValue();
        for (int idx = 0; idx < nodeList.size(); idx++){
            ItemSetNode itemSetNode = nodeList.get(idx);
            if (itemSetNode.getState()==node.getState())continue;
            if (realHashValue.equals(itemSetNode.getRealHashValue())){
//                if (!realHashValue.equals(itemSetNode.getRealHashValue())){
//                    nodeList.set(idx,unionItemSetNode(itemSetNode,node));
//                }
                return nodeList.get(idx);//another node
            }
        }

        Queue<Pair<Character,ItemSetNode>> childQueue = new LinkedList<>();
        char[] branchId = new char[256];branchId[0]=1;

        //现在扩展项的孩子部分，这部分只需要把已经加入的项按照transferCharacter分类即可
        int itemLength = node.getLength();
        int idx = 0;
        while (idx<itemLength){
            Tri<Integer,Integer,More<Character>> tri_ = node.getItem(idx);
            String rightGrammar = cfg.getGrammar(tri_.getFirst()).getSecond();
            char branchChar = rightGrammar.length()<= tri_.getSecond()?0:rightGrammar.charAt(tri_.getSecond());
            if (branchId[branchChar]==0){
                ItemSetNode child = new ItemSetNode(I_i++);
                for (int j = 0; j < node.getLength(); j++){
                    Tri<Integer,Integer,More<Character>> tri = node.getItem(j);
                    String grammarRight = cfg.getGrammar(tri.getFirst()).getSecond();
                    if (tri.getSecond()>=grammarRight.length())continue;
                    if (branchChar == grammarRight.charAt(tri.getSecond())){
//                        String flag = grammarRight.substring(tri.getSecond()+1);
//                        More<Character> more = tri.getThird();
//                        if (!flag.equals("")){
//                            more = unionCheckFlag(more,FIRST.first(cfg,flag));
//                        }
                        child.addItem(tri.getFirst(),tri.getSecond()+1,tri.getThird());
                    }
                }
                branchId[branchChar] = 1;
                node.addChild(branchChar,child);
                childQueue.add(new Pair<>(branchChar,child));
            }
            idx++;
        }
        while (!childQueue.isEmpty()){
            Pair<Character,ItemSetNode> pair = childQueue.poll();
            ItemSetNode child = pair.getSecond();
            child = bfs(child);
            node.setChild(pair.getFirst(),child);
        }
        return node;
    }

    private ItemSetNode getSameHashNode(String hashValue, boolean isSimple){
        for (ItemSetNode node : nodeList){
            if (isSimple){
                if (node.getSimpleHashValue().equals(hashValue))return node;
            }else{
                if (node.getRealHashValue().equals(hashValue))return node;
            }
        }
        return null;
    }

    private More<Character> unionCheckFlag(More<Character> checkFlag1, More<Character> checkFlag2){
        List<Character> chs = checkFlag2.getAllItems();
        for (char c : chs){
            if (!checkFlag1.containsKey(c))
                checkFlag1.addItem(c);
        }
        return checkFlag1;
    }

    //合并两个项的检测符，返回第一个
    //precondition: two nodes' products and dot's position are the same
    private ItemSetNode unionItemSetNode(ItemSetNode node1, ItemSetNode node2){
        for (int i = 0; i < node2.getLength(); i++){
            Tri<Integer,Integer,More<Character>> tre = node2.getItem(i);
            Pair<Integer, Tri<Integer,Integer,More<Character>>> pair = node1.getItem(tre.getFirst(),tre.getSecond());
            More<Character> newMore = unionCheckFlag(tre.getThird(),pair.getSecond().getThird());
            pair.getSecond().setThird(newMore);
            node1.setItem(pair.getFirst(),pair.getSecond());
        }
        return node1;
    }
}
